package leetcode.D1000.T921;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-02-18 21:05:50 星期五
 */

class Solution {
    // 一刷
    /*public int minAddToMakeValid(String s) {
        Deque<Character> dq = new LinkedList<>();
        for(int i=0; i<s.length(); ++i) {
            if (dq.isEmpty()) {
                dq.addFirst(s.charAt(i));
                continue;
            }
            if (s.charAt(i) == ')' && dq.getFirst().equals('(')) {
                dq.removeFirst();
            } else
                dq.addFirst(s.charAt(i));
        }
        return dq.size();
    }*/

    // 二刷
    public int minAddToMakeValid(String s) {
        int ans = 0, left = 0;
        for (int i=0; i<s.length(); ++i) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                if (left > 0)
                    left--;
                else
                    ans++;
            }
        }
        return ans + left;
    }
}